In the Long Term Evolution (LTE) system of the third generation radio communication, convolutional coding is widely applied to the channels such as the Broadcast Channel (BCH), the Downlink Control Information (DCI) channel and the Uplink Control Information (UCI) channel. For improving coding rate and performance, the tail biting convolutional coding is adopted to perform channel coding in the LTE system.
The structure of an encoder of the tail biting convolutional coding adopted in the LTE system is shown in FIG. 1. The encoding rate of the tail biting convolutional coding is 1/3. The initial value of state register of the encoder is set as the corresponding value of the last 6 information bits of input data stream, so as to make the initial state of the shift register be the same as the final state of the shift register.
At present, the decoding method of the tail biting convolutional code usually is the Viterbi algorithm, which mainly comprises the following steps.
Step 1: computing the path metric value according to the input data to be decoded, and accumulating the path metric value to the original state metric value to obtain a new state metric value.
Step 2: keeping 64 maximum state metric values through the add-compare-select processing, and saving the selection path, wherein the path relationship diagram of the add-compare-select processing is shown in FIG. 3.
Step 3: because of tail biting, Step 1 and Step 2 can be repeated until the decoding performance meets the requirement, as shown in FIG. 2.
Step 4: backtracking. The state of the tail biting convolution is not returned to zero, so that the backtracking can start either from any state point or from the point of the maximum state metric value.
Because the correctness of data at backtracking point cannot be ensured when backtracking from any state point, a certain backtracking depth is required to ensure that the backtracking path is stabilized to the surviving path (the backtracking depth is usually 5 to 10 times of the constraint length). Thus, for achieving the same performance, backtracking from any state point needs more computing time and more storage resource of path than backtracking from the point of the maximum state metric value.
The advantage of backtracking from the point of the maximum state metric value is that: the maximum state metric conforms to the most fundamental principle of the Viterbi decoding: the maximum likelihood principle. Hence, the point of the maximum state metric value is the starting point of the surviving path. The confidence of the data backtracked from this point is highest, and the data can be directly output as the decoded data without needing to compute the data with large backtracking depth or to save storage resource of this path. The disadvantage of backtracking from the point of the maximum state metric value is that: certain resource is needed to search for the point of the maximum state metric value, and the maximum value is selected from 64 state metric values.
Searching for the maximum value in 64 state metric values is a searching problem. At present, for hardware implementation, there are usually two methods, namely, the serial comparison and the parallel comparison. The serial comparison needs only one comparator, but needs to compare for 64 times in order. The serial comparison needs longer comparison time, and thus wastes time. If the parallel comparison wants to obtain the maximum value by comparing with only one step, it needs 63 comparators, thereby needing more comparison resource.